SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Loop optimization</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Loop optimization</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about compiler optimization for loops. For the more specific technique of overhead reduction of loop nests, see <a href="Loop_nest_optimization" title="Loop nest optimization">Loop nest optimization</a>.</div>

<p>In <a href="Compiler_theory" class="mw-redirect" title="Compiler theory">compiler theory</a>, <b>loop optimization</b> is the process of increasing execution speed and reducing the overheads associated with <a href="Control_flow#Loops" title="Control flow">loops</a>. It plays an important role in improving <a href="Cache_(computing)" title="Cache (computing)">cache</a> performance and making effective use of <a href="Parallel_computing" title="Parallel computing">parallel processing</a> capabilities. Most execution time of a <a href="Scientific_computing" class="mw-redirect" title="Scientific computing">scientific program</a> is spent on loops; as such, many <a href="Compiler_optimization" class="mw-redirect" title="Compiler optimization">compiler optimization</a> techniques have been developed to make them faster.

</p>

<div class="mw-heading mw-heading2"><h2 id="Representation_of_computation_and_transformations">Representation of computation and transformations</h2></div>

<p>Since instructions inside loops can be executed repeatedly, it is frequently not possible to give a bound on the number of instruction executions that will be impacted by a loop optimization. This presents challenges when reasoning about the correctness and benefits of a loop optimization, specifically the representations of the computation being optimized and the optimization(s) being performed.<sup id="cite_ref-Collard_1-0" class="reference"><a href="#cite_note-Collard-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Optimization_via_a_sequence_of_loop_transformations">Optimization via a sequence of loop transformations</h2></div>

<p>Loop optimization can be viewed as the application of a sequence of specific <b>loop transformations</b> (listed below or in <i>Compiler transformations for high-performance computing</i><sup id="cite_ref-UCB_2-0" class="reference"><a href="#cite_note-UCB-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>) to the source code or <a href="Intermediate_representation" title="Intermediate representation">intermediate representation</a>, with each <a href="Program_transformation" title="Program transformation">transformation</a> having an associated test for legality. A transformation (or sequence of transformations) generally must preserve the temporal sequence of all <a href="Data_dependency" title="Data dependency">dependencies</a> if it is to preserve the result of the program (i.e., be a legal transformation). Evaluating the benefit of a transformation or sequence of transformations can be quite difficult within this approach, as the application of one beneficial transformation may require the prior use of one or more other transformations that, by themselves, would result in reduced performance.

</p><p>Common loop transformations include:

</p>

<ul><li><a href="Loop_fission" class="mw-redirect" title="Loop fission">Fission</a> or distribution – loop fission attempts to break a loop into multiple loops over the same index range, but each new loop takes only part of the original loop's body. This can improve <a href="Locality_of_reference" title="Locality of reference">locality of reference</a>, both of the data being accessed in the loop and the code in the loop's body.</li>

<li><a href="Loop_fusion" class="mw-redirect" title="Loop fusion">Fusion</a> or combining – this combines the bodies of two adjacent loops that would iterate the same number of times (whether or not that number is known at compile time), as long as they make no reference to each other's data.</li>

<li><a href="Loop_interchange" title="Loop interchange">Interchange</a> or permutation – these optimizations exchange inner loops with outer loops. When the loop variables index into an array, such a transformation can improve locality of reference, depending on the array's layout.</li>

<li><a href="Loop_inversion" title="Loop inversion">Inversion</a> – this technique changes a standard <i>while</i> loop into a <i>do/while</i> (a.k.a. <i>repeat/until</i> ) loop wrapped in an <i>if</i> conditional, reducing the number of jumps by two for cases where the loop is executed. Doing so duplicates the condition check (increasing the size of the code) but is more efficient because jumps usually cause a <a href="Pipeline_stall" title="Pipeline stall">pipeline stall</a>. Additionally, if the initial condition is known at compile-time and is known to be <a href="Side-effect_(computer_science)" class="mw-redirect" title="Side-effect (computer science)">side-effect</a>-free, the initial <i>if</i>-guard can be skipped.</li>

<li><a href="Loop-invariant_code_motion" title="Loop-invariant code motion">Loop-invariant code motion</a> – this can vastly improve efficiency by moving a computation from inside the loop to outside of it, computing a value just once before the loop begins, if the resultant quantity of the calculation will be the same for every loop iteration (i.e., a loop-invariant quantity). This is particularly important with address-calculation expressions generated by loops over arrays. For correct implementation, this technique must be used with inversion, because not all code is safe to be moved outside the loop.</li>

<li><a href="Loop-level_parallelism" title="Loop-level parallelism">Parallelization</a> – this is a special case of <a href="Automatic_parallelization" title="Automatic parallelization">automatic parallelization</a> focusing on loops, restructuring them to run efficiently on multiprocessor systems. It can be done automatically by compilers (<a href="Automatic_parallelization" title="Automatic parallelization">automatic parallelization</a>) or manually (inserting parallel directives like <a href="OpenMP" title="OpenMP">OpenMP</a>).</li>

<li>Reversal – a subtle optimization that reverses the order in which values are assigned to the index variable. This can help eliminate <a href="Dependence_analysis" title="Dependence analysis">dependencies</a> and thus enable other optimizations. Certain architectures utilize looping constructs at <a href="Assembly_language" title="Assembly language">assembly</a> level that count in a single direction only (e.g., decrement-jump-if-not-zero [DJNZ]<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>).</li>

<li><a href="Loop_scheduling" title="Loop scheduling">Scheduling</a> – this divides a loop into multiple parts that may be run concurrently on multiple processors.</li>

<li><a href="Loop_skewing" class="mw-redirect" title="Loop skewing">Skewing</a> – this technique is applied to a nested loop iterating over a multidimensional array, where each iteration of the <a href="Inner_loop" title="Inner loop">inner loop</a> depends on previous iterations, and rearranges its array accesses so that the only dependencies are between iterations of the outer loop.</li>

<li><a href="Software_pipelining" title="Software pipelining">Software pipelining</a> – a type of <a href="Out-of-order_execution" title="Out-of-order execution">out-of-order execution</a> of loop iterations to hide the latencies of processor function units.</li>

<li><a href="Loop_splitting" title="Loop splitting">Splitting</a> or peeling – this attempts to simplify a loop or eliminate <a href="Dependence_analysis" title="Dependence analysis">dependencies</a> by breaking it into multiple loops which have the same bodies but iterate over different portions of the index range. A special case is <i>loop peeling</i>, which can simplify a loop with a problematic first iteration by performing that iteration separately before entering the loop.</li>

<li><a href="Loop_tiling" class="mw-redirect" title="Loop tiling">Tiling</a> or blocking – reorganizes a loop to iterate over blocks of data sized to fit in the cache.</li>

<li><a href="Automatic_vectorization" title="Automatic vectorization">Vectorization</a> – attempts to run as many of the loop iterations as possible at the same time on a <a href="SIMD" class="mw-redirect" title="SIMD">SIMD</a> system.</li>

<li><a href="Loop_unrolling" title="Loop unrolling">Unrolling</a> – duplicates the body of the loop multiple times, in order to decrease the number of times the loop condition is tested and the number of jumps, which may degrade performance by impairing the instruction pipeline. Completely unrolling a loop eliminates all overhead (except multiple instruction fetches and increased program load time), but requires that the number of iterations be known at compile time (except in the case of <a href="Just-in-time_compilation" title="Just-in-time compilation">Just-in-time compilation</a>). Care must also be taken to ensure that multiple re-calculation of indexed variables is not a greater overhead than advancing pointers within the original loop.</li>

<li><a href="Loop_unswitching" title="Loop unswitching">Unswitching</a> – moves a conditional from inside a loop to outside of it by duplicating the loop's body, and placing a version of it inside each of the <i>if</i> and <i>else</i> clauses of the conditional.</li>

<li><a href="Loop_sectioning" title="Loop sectioning">Sectioning</a> or strip-mining – introduced for <a href="Vector_processor" title="Vector processor">vector processors</a>, loop-sectioning is a loop-transformation technique for enabling <a href="SIMD" class="mw-redirect" title="SIMD">SIMD</a> (single instruction, multiple data)-encodings of loops and improving memory performance. This involves each vector operation being done for a size less-than or equal-to the maximum vector length on a given vector machine.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading3"><h3 id="The_unimodular_transformation_framework">The unimodular transformation framework</h3></div>

<p>The unimodular transformation approach<sup id="cite_ref-Muchnick_6-0" class="reference"><a href="#cite_note-Muchnick-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> uses a single <a href="Unimodular_matrix" title="Unimodular matrix">unimodular matrix</a> to describe the combined result of a sequence of many of the above transformations. Central to this approach is the view of the set of all executions of a statement within <i>n</i> loops as a set of integer points in an <i>n</i>-dimensional space, with the points being executed in <a href="Lexicographical_order" class="mw-redirect" title="Lexicographical order">lexicographical order</a>. For example, the executions of a statement nested inside an outer loop with index <i>i</i> and an inner loop with index <i>j</i> can be associated with the pairs of integers <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i,j)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i,j)}</annotation>

</semantics>

</math></span><img src="./8ef21910f980c6fca2b15bee102a7a0d861ed712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.604ex; height:2.843ex;" alt="{\displaystyle (i,j)}" loading="lazy"></span>⁠</span>. The application of a unimodular transformation corresponds to the multiplication of the points within this space by the matrix. For example, the interchange of two loops corresponds to the matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&1\\1&0\end{bmatrix}}}">

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&1\\1&0\end{bmatrix}}}</annotation>

</semantics>

</math></span><img src="./cc64578eb51f34058527d6bb06d6162a1908de83.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&1\\1&0\end{bmatrix}}}" loading="lazy"></span>.

</p><p>A unimodular transformation is legal if it preserves the temporal sequence of all <a href="Data_dependency" title="Data dependency">dependencies</a>; measuring the performance impact of a unimodular transformation is more difficult. Imperfectly nested loops and some transformations (such as tiling) do not fit easily into this framework.

</p>

<div class="mw-heading mw-heading3"><h3 id="The_polyhedral_or_constraint-based_framework">The polyhedral or constraint-based framework</h3></div>

<p>The <a href="Polytope_model" title="Polytope model">polyhedral model</a><sup id="cite_ref-AK_7-0" class="reference"><a href="#cite_note-AK-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> handles a wider class of programs and transformations than the unimodular framework. The set of executions of a set of statements within a possibly imperfectly nested set of loops is seen as the union of a set of polytopes representing the executions of the statements. <a href="Affine_transformation" title="Affine transformation">Affine transformations</a> are applied to these polytopes, producing a description of a new execution order. The boundaries of the polytopes, the data dependencies, and the transformations are often described using systems of constraints, and this approach is often referred to as a <b>constraint-based</b> approach to loop optimization. For example, a single statement within an outer loop '<style data-mw-deduplicate="TemplateStyles:r886049734">

/* start https://en.wikipedia.org/ */

.mw-parser-output .monospaced{font-family:monospace,monospace}

/* end https://en.wikipedia.org/ */

</style><span class="monospaced">for i := 0 to n</span>' and an inner loop '<span class="monospaced">for j := 0 to i+2</span>' is executed once for each <span class="monospaced">(i, j)</span> pair such that <span class="monospaced">0 <= i <= n and 0 <= j <= i+2</span>.

</p><p>Once again, a transformation is legal if it preserves the temporal sequence of all <a href="Data_dependency" title="Data dependency">dependencies</a>. Estimating the benefits of a transformation, or finding the best transformation for a given code on a given computer, remain the subject of ongoing research as of the time of this writing (2010).

</p>

<ul><li><a href="Loop_nest_optimization" title="Loop nest optimization">Loop nest optimization</a></li>

<li><a href="Polytope_model" title="Polytope model">Polytope model</a></li>

<li><a href="Scalable_parallelism" title="Scalable parallelism">Scalable parallelism</a></li>

<li><a href="Scalable_locality" title="Scalable locality">Scalable locality</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

<li id="cite_note-Collard-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-Collard_1-0">^</a></b></span> <span class="reference-text">In the book <i><a rel="nofollow" class="external text" href="https://books.google.com/books?id=8FbTZc4pa-cC&q=%22loop+optimization%22">Reasoning About Program Transformations</a></i>, Jean-Francois Collard discusses in depth the general question of representing executions of programs rather than program text in the context of static optimization.</span>

</li>

<li id="cite_note-UCB-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-UCB_2-0">^</a></b></span> <span class="reference-text">David F. Bacon, <a href="Susan_L._Graham" title="Susan L. Graham">Susan L. Graham</a>, and Oliver J. Sharp. <i>Compiler transformations for high-performance computing.</i> Report No. UCB/CSD 93/781, Computer Science Division-EECS, University of California, Berkeley, Berkeley, California 94720, November 1993 (available at <a href="CiteSeer" class="mw-redirect" title="CiteSeer">CiteSeer</a> <a rel="nofollow" class="external autonumber" href="http://citeseer.ist.psu.edu/bacon93compiler.html">[1]</a>). Introduces compiler analysis such as data dependence analysis and interprocedural analysis, as well as a very complete list of loop transformations</span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.win.tue.nl/~aeb/comp/8051/set8051.html-orig#51djnz">"8051 Instruction Set"</a>. <i>www.win.tue.nl</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-12-09</span></span>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://software.intel.com/en-us/articles/strip-mining-to-optimize-memory-use-on-32-bit-intel-architecture/">"Intel Developer Zone"</a>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://download.oracle.com/docs/cd/E19205-01/819-5262/aeugr/index.html">"7.6.3.1 Strip-Mining (Sun Studio 12: Fortran Programming Guide)"</a>.</cite></span>

</li>

<li id="cite_note-Muchnick-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-Muchnick_6-0">^</a></b></span> <span class="reference-text">Steven S. Muchnick, <i><a rel="nofollow" class="external text" href="https://books.google.com/books?id=Pq7pHwG1_OkC&q=%22unimodular+transformation%22">Advanced Compiler Design and Implementation</a>,</i> 1997 Morgan Kaufmann. Section 20.4.2 discusses loop optimization.</span>

</li>

<li id="cite_note-AK-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-AK_7-0">^</a></b></span> <span class="reference-text">R. Allen and K. Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann, 2002.</span>

</li>

</ol></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Compiler_optimizations253" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Compiler_optimizations253" style="font-size:114%;margin:0 4em"><a href="Optimizing_compiler" title="Optimizing compiler">Compiler optimizations</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Basic block</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Peephole_optimization" title="Peephole optimization">Peephole optimization</a></li>

<li><a href="Local_value_numbering" class="mw-redirect" title="Local value numbering">Local value numbering</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatic_parallelization" title="Automatic parallelization">Automatic parallelization</a></li>

<li><a href="Automatic_vectorization" title="Automatic vectorization">Automatic vectorization</a></li>

<li><a href="Induction_variable" title="Induction variable">Induction variable</a></li>

<li><a href="Loop_fusion" class="mw-redirect" title="Loop fusion">Loop fusion</a></li>

<li><a href="Loop-invariant_code_motion" title="Loop-invariant code motion">Loop-invariant code motion</a></li>

<li><a href="Loop_inversion" title="Loop inversion">Loop inversion</a></li>

<li><a href="Loop_interchange" title="Loop interchange">Loop interchange</a></li>

<li><a href="Loop_nest_optimization" title="Loop nest optimization">Loop nest optimization</a></li>

<li><a href="Loop_splitting" title="Loop splitting">Loop splitting</a></li>

<li><a href="Loop_unrolling" title="Loop unrolling">Loop unrolling</a></li>

<li><a href="Loop_unswitching" title="Loop unswitching">Loop unswitching</a></li>

<li><a href="Software_pipelining" title="Software pipelining">Software pipelining</a></li>

<li><a href="Strength_reduction" title="Strength reduction">Strength reduction</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data-flow_analysis" title="Data-flow analysis">Data-flow<br>analysis</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Available_expression" title="Available expression">Available expression</a></li>

<li><a href="Common_subexpression_elimination" title="Common subexpression elimination">Common subexpression elimination</a></li>

<li><a href="Constant_folding" title="Constant folding">Constant folding</a></li>

<li><a href="Dead_store" title="Dead store">Dead store</a> elimination</li>

<li><a href="Induction_variable_recognition_and_elimination" class="mw-redirect" title="Induction variable recognition and elimination">Induction variable recognition and elimination</a></li>

<li><a href="Live-variable_analysis" title="Live-variable analysis">Live-variable analysis</a></li>

<li><a href="Upwards_exposed_uses" title="Upwards exposed uses">Upwards exposed uses</a></li>

<li><a href="Use-define_chain" title="Use-define chain">Use-define chain</a></li>

<li><a href="Reaching_definition" title="Reaching definition">Reaching definitions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Static_single-assignment_form" title="Static single-assignment form">SSA</a>-based</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Global_value_numbering" class="mw-redirect" title="Global value numbering">Global value numbering</a></li>

<li><a href="Sparse_conditional_constant_propagation" title="Sparse conditional constant propagation">Sparse conditional constant propagation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Code_generation_(compiler)" title="Code generation (compiler)">Code generation</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Instruction_scheduling" title="Instruction scheduling">Instruction scheduling</a></li>

<li><a href="Instruction_selection" title="Instruction selection">Instruction selection</a></li>

<li><a href="Register_allocation" title="Register allocation">Register allocation</a></li>

<li><a href="Rematerialization" title="Rematerialization">Rematerialization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Functional</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Deforestation_(computer_science)" title="Deforestation (computer science)">Deforestation</a></li>

<li><a href="Tail_call" title="Tail call">Tail-call elimination</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Global</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interprocedural_optimization" title="Interprocedural optimization">Interprocedural optimization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bounds-checking_elimination" title="Bounds-checking elimination">Bounds-checking elimination</a></li>

<li><a href="Compile-time_function_execution" title="Compile-time function execution">Compile-time function execution</a></li>

<li><a href="Dead-code_elimination" title="Dead-code elimination">Dead-code elimination</a></li>

<li><a href="Expression_templates" title="Expression templates">Expression templates</a></li>

<li><a href="Inline_expansion" title="Inline expansion">Inline expansion</a></li>

<li><a href="Jump_threading" title="Jump threading">Jump threading</a></li>

<li><a href="Partial_evaluation" title="Partial evaluation">Partial evaluation</a></li>

<li><a href="Profile-guided_optimization" title="Profile-guided optimization">Profile-guided optimization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Static analysis</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alias_analysis" title="Alias analysis">Alias analysis</a></li>

<li><a href="Array-access_analysis" title="Array-access analysis">Array-access analysis</a></li>

<li><a href="Control-flow_analysis" title="Control-flow analysis">Control-flow analysis</a></li>

<li><a href="Data-flow_analysis" title="Data-flow analysis">Data-flow analysis</a></li>

<li><a href="Dependence_analysis" title="Dependence analysis">Dependence analysis</a></li>

<li><a href="Escape_analysis" title="Escape analysis">Escape analysis</a></li>

<li><a href="Pointer_analysis" title="Pointer analysis">Pointer analysis</a></li>

<li><a href="Shape_analysis_(program_analysis)" title="Shape analysis (program analysis)">Shape analysis</a></li>

<li><a href="Value_range_analysis" title="Value range analysis">Value range analysis</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-04-06" href="https://en.wikipedia.org/wiki/?title=Loop_optimization&oldid=1217570678">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>